import java.util.ArrayList;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 09 - 03
 * Time: 10:55
 */
//牛客 表达式求值
public class Solution4 {
    //官方推荐方法 栈+递归+顺序表
    public ArrayList<Integer> solveF(String s, int index) {
        Stack<Integer> stack = new Stack<>();
        int num = 0;
        char op = '+';
        int i = 0;//i不要定义到for循环中，因为下面的for循环外也要用到i
        for (i = index; i < s.length(); i++) {
            if(s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                num = num * 10 + s.charAt(i) - '0';
                if(i != s.length() - 1) {
                    continue;
                }
            }
            if(s.charAt(i) == '(') {
                ArrayList<Integer> temp = solveF(s, i + 1);//左右括号包起来的东西当成一个数
                num = temp.get(0);
                i = temp.get(1);
                if(i != s.length() - 1) {
                    continue;
                }
            }
            switch (op) {//遇到i为算术运算符时，依据之前用op保留的算术运算符和i前面的num结合成相应的“num"再放入栈中
                case '+':
                    stack.push(num);
                    break;
                case '-':
                    stack.push(-num);
                    break;
                case '*':
                    int temp = stack.pop();
                    stack.push(temp * num);
                    break;
            }
            num = 0;//每在栈中更新一个"num"，num都要初始化为0
            if(s.charAt(i) == ')') {
                break;
            }else {
                op = s.charAt(i);
            }
        }
        int sum = 0;
        while (!stack.isEmpty()) {
            sum += stack.pop();
        }
        ArrayList<Integer> res = new ArrayList<>();
        res.add(sum);
        res.add(i);
        return res;
    }
    public int solve (String s) {
        ArrayList<Integer> temp = solveF(s, 0);
        return temp.get(0);
    }
}
